package name.huzhenbo.java.algorithm.graph;

/**
 * Prim is the person who found this alorithm.
 */
class PrimMinSpanTree {
    private Edge[] closedges;
    private Graph graph;

    public PrimMinSpanTree(Graph graph) {
        this.graph = graph;
        closedges = new Edge[graph.vertexNum()];
    }

    /**
     * O(n2)
     *
     * @return The min spans
     */
    public int prim() {
        // start from 0, but actually it can start from anyone
        int k = 0;

        for (int i = 0; i < closedges.length; i++) {
            closedges[i] = new Edge(k, graph.weight(k, i));
        }

        int spans = 0;
        for (int i = 1; i < graph.vertexNum(); i++) {
            k = nextVertex(closedges);
            spans += closedges[k].weight;
            span(k);

            // Set all included vertex to 0, 0 is used as a flag indicating included vertex
            closedges[k].weight = 0;

            for (int j = 0; j < graph.vertexNum(); j++) {
                if (graph.weight(k, j) > 0) {
                    if (closedges[j].weight == -1 || graph.weight(k, j) < closedges[j].weight){
                        closedges[j] = new Edge(k, graph.weight(k, j));
                    }
                }
            }
        }
        return spans;
    }

    private void span(int end) {
        Edge edge = closedges[end];
        System.out.println("From " + new Integer(edge.start) + " to " + new Integer(end) + ": "
                + new Integer(edge.weight));
    }

    private int nextVertex(Edge[] closedges) {
        int min = Integer.MAX_VALUE;
        int t = -1;
        for (int i = 0; i < closedges.length; i++) {
            // skip included vertex and the vertext not yet connected yet
            if (closedges[i].weight > 0 && closedges[i].weight < min) {
                min = closedges[i].weight;
                t = i;
            }
        }
        return t;
    }

    /**
     * Start: start vertex index
     * Weight: the weight from start to end
     * End: the end is the index of this edge in the closedges
     */
    private class Edge {
        private int start;
        private int weight;

        public Edge(int start, int weight) {
            this.start = start;
            this.weight = weight;
        }
    }
}
